The present invention relates generally to the field of databases, and more particularly to database access optimization techniques.
A user queries a database by submitting one or more conditions or constraints that the data sought must meet. The database searches for data, often in tables, that fulfill the constraints and returns the data to a user. A database search can consume a considerable amount of system resources (e.g., CPU cycles, memory, interconnect bandwidth, and disk space) that can depend on a number of things—including the amount of data in the database, the structure of the data, the conditions that the requested data must meet, and the distribution of the requested data in the database. To facilitate access to a database, often one or more indexes into the database is formed. Usually a database index is a table that contains information about a particular column of data in a database table (i.e., a column in a table in the database). The index often contains one entry for each unique value in the column that the index represents. The entry for a unique value contains the address(s) (i.e., record identifier(s) or RIDs) of the information in the row(s) in the database table that contain the unique value. Therefore, an index enables relatively efficient access to the rows of data that contain specific data in a column of a table. Often, more than one index is formed on the same table, one index for each column of interest in the table.
Because a database query can be complex and can consume significant computational resources, a data base query optimizer is usually invoked to generate a query plan that attempts to utilize resources efficiently and decrease execution time. In general, such a query plan partitions a query into a sequence of database accesses in an attempt to minimize the total number of rows that must be accessed and processed to fulfill the conditions and constraints on the data requested by the query. For example, it is efficient to execute that part of a query first that effects the greatest decrease in the search space for subsequent parts of the query.